[Coding043] LeetCode 143

Reorder List

More coding records

Get the knowledge flowing and circulating! :)

目录

※ 本题收获

这个程序差点让我放弃编程！

看上去本来很简单，但是思路比较混乱，同时也让我感觉，似乎并不是一天的任何时间都适合编程的，就比如下午15:00左右做这个程序，搞到17:40才把程序的流程理清，到了18:00才最终把文档写完！😓

难点在哪呢？总的来说，还是思路不清。

首先：指针混用，一开始的程序写的时候，有时候用了newStart，有的用了dummy，有的p，有的q，有的r1，有的r2，真是晕头转向。

• 解法：理清思路再Coding！

然后：思路模糊，一开始用cnt，cnt--（都等于0了）结束了！最后程序我还在用cnt这个为0的变量来辅助衔接链表。

• 解法：变量前期定义清楚之后，再在后期使用。不要胡乱定义，到处使用。

最后，我想说，不要小看任何一个程序，每个程序都要认真对待。从一开始的时候，就要思路清晰，否则越来越混乱，最后还要重新再理，何苦呢？浪费了时间还消磨了耐心！切记！

这个程序的收获：

• 从一个链表（5→6→7→8→9→null）挪到另一个链表（dummy→null）的操作【需要明确知道要完成的是什么，如下手绘图中的第一个绿色粗圈】；

• 两个链表交替衔接的时候，需要清楚地知道从何处断，断了之后又当如何衔接？

  • line51 & line59是一套连招！必须相辅相成，同时存在！

题目：143. Reorder List

You are given the head of a singly linked-list. The list can be represented as:

xxxxxxxxxx
1
1
L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

xxxxxxxxxx
1
1
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

xxxxxxxxxx
2
1
Input: head = [1,2,3,4]
2
Output: [1,4,2,3]

Example 2:

xxxxxxxxxx
2
1
Input: head = [1,2,3,4,5]
2
Output: [1,5,2,4,3]

Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].

• 1 <= Node.val <= 1000

代码1（配 · 手绘过程图）

xxxxxxxxxx
63
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public void reorderList(ListNode head) {
13
        ListNode p = head;
14
        int cnt = 0;
15
        while (p != null)
16
        {
17
            cnt++;
18
            p = p.next;
19
        }
20

21
        int start = cnt / 2;
22
        
23
        ListNode newStart = head;
24
        while (start-- != 0)
25
        {
26
            newStart = newStart.next;
27
        }
28

29
        // System.out.println(newStart.val);
30

31
        ListNode dummy = new ListNode(0);
32

33
        ListNode q = newStart.next;
34
        while (q != null)
35
        {            
36
            // 这一句同时将原链表截断：newStart.next最后会指向链表的尾部（null）
37
            newStart.next = q.next;  // 防止链表断裂
38

39
            // 此时可以操作q了
40
            q.next = dummy.next;
41
            dummy.next = q;
42

43
            q = newStart.next;  // 开始处理新的q
44
        }
45

46
        p = head;
47
        q = dummy.next;
48
        
49
        while (q != null)  // 把短的插入长的里面
50
        {
51
            dummy.next = q.next;  // 防止断裂操作1
52

53
            // 把q塞到p的后面，并保证不要断裂
54
            q.next = p.next;
55
            p.next = q;
56
            // 让p继续移动到下一个待处理的地方
57
            p = q.next;
58

59
            q = dummy.next;  // 防止断裂操作2
60
        }
61
        return;
62
    }
63
}

获取链表的两半：

合并链表的两半：

代码解读 | 评价

程序的思路比较简单：

1. 首先把链表分为两半；

   • 方法有很多：

     • 可以用cnt计数，然后cnt/2；

     • 也可以用双指针，一个跑的快，一个跑的慢；跑的快的变为null了，跑的慢的刚好指向中间的那个分割点。

2. 后一半逆序

3. 然后把第一半和最后一半交替接起来。